

//1591.奇怪的打印机II
class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        int n = targetGrid.size(),m=targetGrid[0].size();
        int num = 0;
        for(int i = 0 ;i < n;i++)
        for(int j = 0 ;j < m;j++) num=max(num,targetGrid[i][j]);  //找出矩阵中最大的数
        vector<bool> col(num+1,true);       //用来标记有哪些数字被使用
        vector<vector<int>> part(num+1,vector<int>(4,-1)); //0:left 1:up 2:down 3:right
        for(int i = 0;i < n;i++)
        {
            for(int j = 0; j < m ;j++)
            {
                int k = targetGrid[i][j];
                part[k][0] = part[k][0]==-1?j:min(part[k][0],j);
                part[k][1] = part[k][1]==-1?i:min(part[k][1],i);
                part[k][2] = part[k][2]==-1?i:max(part[k][2],i);
                part[k][3] = part[k][3]==-1?j:max(part[k][3],j);
                col[k] = false;  //对使用过的数字进行标记
            }                
        }        

        vector<set<int>> l(num+1);  //记录每个数字覆盖了那些数字,此处使用set的目的是为了去重
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                int x = targetGrid[i][j];
                for(int k = 1;k <= num ;k++)
                {
                    if(part[k][0] <= j && part[k][1] <= i
                        &&part[k][2] >= i && part[k][3] >= j && k != x)   //x覆盖了k
                        l[x].insert(k);
                }
            }
        }

        unordered_map<int,int> count_m;  //记录每个数字被覆盖了几次
        for(int i = 1;i <= num ;i++)
        {
            auto& st = l[i];
            for(auto& x: st) count_m[x]++;
        } 

        queue<int> q;  //记录没有被覆盖的数字
        for(int i = 1;i <= num;i++)
            if(count_m.count(i)==0 && col[i]==false) q.push(i);

        //从最外层开始取,看是否可以取出来
        while(!q.empty())
        {
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                int f = q.front();
                q.pop();
                col[f]=true;     //将颜色去除
                auto& st = l[f];
                for(auto& x: st)
                    if(--count_m[x]==0) 
                        q.push(x);
            }
        }         
        return col==vector<bool>(num+1,true);   //检查是否所有元素都被去除
    }
};